package comprehensive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Exercises10 {
    // N皇后
    // 非常重要的题
    // 方法二：利用数学规则(y = (+/-)x + b)和哈希表进行判断
    boolean[] cheackCol; // 判断要放入“皇后”的位置的对应的那一列
    boolean[] cheackDig1; // 用于判断要放入“皇后”的位置的主对角线
    boolean[] cheackDig2; // 用于判断要放入“皇后”的位置的副对角线
    List<List<String>> ret; // 返回
    char[][] path; // 用于拼接
    int nn;

    public List<List<String>> solveNQueens2(int n) {
        nn = n;
        cheackCol = new boolean[n];
        cheackDig1 = new boolean[n*2]; // 这里的对角线的个数是2*n减一的个数，所以创建一个2*n的个数
        cheackDig2 = new boolean[n*2];
        ret = new ArrayList<>();
        path = new char[n][n];

        // 把n*n的整个棋盘都放入‘.’ 之后只需要关心皇后‘Q’ 放入的位置就可以了
        for(int i = 0;i < n;i++) {
            Arrays.fill(path[i],'.');
        }

        dfs1(0);

        return ret;
    }

    public void dfs1(int row) { // row是行，col是列
        if(row == nn) {
            // 这个时候是可以把path中的值放入到ret中，因为这个时候就是把“皇后”都放只完成了
            List<String> tmp = new ArrayList<>();
            for(int i = 0;i < nn;i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(tmp);
        }

        for(int col = 0;col < nn;col++) {
            //进行剪枝，判断是否可以放入“皇后”
            // 这里使用的是 数学中的 y(row) = x(col) + b (正对角线) y = -x + b (副对角线)
            // 在一个对角线上 y - x = b 或者 y + x = b
            // 每次放入的时候，如判断放入的位置的 主对角线和符对角线是否是false
            // 这里要注意一下，在主对角线的时候呢，右下面的对角线如果按照正常计算可能会到达负数。所以我们要添加一个偏移量
            if(cheackCol[col] == false && cheackDig1[row - col + nn] == false && cheackDig2[row + col] == false) {
                path[row][col] = 'Q';
                cheackCol[col] = cheackDig1[row - col + nn] = cheackDig2[row + col] = true;

                dfs1(row + 1);

                path[row][col] = '.';
                cheackCol[col] = cheackDig1[row - col + nn] = cheackDig2[row + col] = false;
            }
        }
    }

    // 方式一：在判断是否可以放“皇后”的条件使用for循环遍历
    List<List<String>> ret1;
    char[][] path1;
    int count;

    public List<List<String>> solveNQueens(int n) {
        count = n;
        ret1 = new ArrayList<>();
        path1 = new char[n][n];

        for(int i = 0;i < n;i++) {
            Arrays.fill(path1[i],'.'); // 把二维数组全部放入 ","
        }

        dfs(0);

        return ret1;
    }

    public void dfs(int row) {
        // 这里传入的相当于是第几行

        if(count == row) { // 因为是从0开始的
            // 这就说明把所有的行数里面都添加上了“皇后”，那么就可以把其放入到ret中
            List<String> tmp = new ArrayList<>();
            for(int i = 0;i < count;i++) {
                tmp.add(new String(path1[i])); // 把每一行放入到tmp中
            }
            ret1.add(new ArrayList<>(tmp)); // 把tmp放入到ret中
        }

        // 进行处理 N皇后
        for(int col = 0;col < count;col++) {
            // 遍历每一行中的每一列可不可以放入数据
            if(isValue(row,col)) {
                // 这时候说明可以进行放入“皇后”
                path1[row][col] = 'Q';
                dfs(row + 1);
                path1[row][col] = '.';
            }
        }
    }

    public boolean isValue(int row,int col) {
        // 判断这一列
        for(int i = 0;i < count;i++) {
            if(path1[i][col] == 'Q') {
                return false;
            }
        }
        // 因为我们是一行一行的进行添加的，所以在放入的这个[row,col]的上面任何位置都不会存在值
        // 所以我们只需要判断 主对角线的左下角，和副对角右下角是否存在“皇后”就可以了

        // 判断主对角线
        for(int i = row - 1,j = col - 1; i >= 0 && j >= 0;i--,j--) {
            if(path1[i][j] == 'Q') {
                return false;
            }
        }
        // 判断副对角线
        for(int i = row - 1,j = col + 1;i >= 0 && j < count;i--,j++){
            if(path1[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
